

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=auto>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/fluid.png">
  <link rel="icon" href="/img/fluid.png">
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=5.0, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="author" content="ShanCe">
  <meta name="keywords" content="">
  
    <meta name="description" content="是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。注意：  每个节点最多有两颗子树，也就是度不大于2 左子树和右子树是有定义的，不能颠倒，即使某个节点只有一颗子树，也有左右之分  1. 概念 根节点：一个树只有一个树根，例如上图 A 就">
<meta property="og:type" content="article">
<meta property="og:title" content="二叉树概念">
<meta property="og:url" content="https://sweetshance.github.io/2023/12/19/%E7%AE%97%E6%B3%95/%E4%BA%8C%E5%8F%89%E6%A0%91/1.%E4%BA%8C%E5%8F%89%E6%A0%91%E6%A6%82%E5%BF%B5/index.html">
<meta property="og:site_name" content="ShanCe的博客">
<meta property="og:description" content="是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。注意：  每个节点最多有两颗子树，也就是度不大于2 左子树和右子树是有定义的，不能颠倒，即使某个节点只有一颗子树，也有左右之分  1. 概念 根节点：一个树只有一个树根，例如上图 A 就">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://sweetshance.github.io/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-1.png">
<meta property="og:image" content="https://sweetshance.github.io/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-2.webp">
<meta property="og:image" content="https://sweetshance.github.io/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-3.jpg">
<meta property="og:image" content="https://sweetshance.github.io/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-4.webp">
<meta property="og:image" content="https://sweetshance.github.io/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-5.webp">
<meta property="og:image" content="https://sweetshance.github.io/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-6.webp">
<meta property="og:image" content="https://sweetshance.github.io/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-7.webp">
<meta property="og:image" content="https://sweetshance.github.io/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-8.webp">
<meta property="og:image" content="https://sweetshance.github.io/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-9.webp">
<meta property="og:image" content="https://sweetshance.github.io/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-10.jpg">
<meta property="og:image" content="https://sweetshance.github.io/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-11.jpg">
<meta property="og:image" content="https://sweetshance.github.io/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-12.webp">
<meta property="og:image" content="https://sweetshance.github.io/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-14.webp">
<meta property="og:image" content="https://sweetshance.github.io/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-15.1.webp">
<meta property="og:image" content="https://sweetshance.github.io/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-15.2.png">
<meta property="og:image" content="https://sweetshance.github.io/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-15.3.webp">
<meta property="article:published_time" content="2023-12-19T08:23:00.000Z">
<meta property="article:modified_time" content="2023-12-21T09:48:14.332Z">
<meta property="article:author" content="ShanCe">
<meta property="article:tag" content="二叉树">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="https://sweetshance.github.io/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-1.png">
  
  
    <meta name="referrer" content="no-referrer-when-downgrade">
  
  
  <title>二叉树概念 - ShanCe的博客</title>

  <link  rel="stylesheet" href="https://lib.baomitu.com/twitter-bootstrap/4.6.1/css/bootstrap.min.css" />



  <link  rel="stylesheet" href="https://lib.baomitu.com/github-markdown-css/4.0.0/github-markdown.min.css" />

  <link  rel="stylesheet" href="https://lib.baomitu.com/hint.css/2.7.0/hint.min.css" />

  <link  rel="stylesheet" href="https://lib.baomitu.com/fancybox/3.5.7/jquery.fancybox.min.css" />



<!-- 主题依赖的图标库，不要自行修改 -->
<!-- Do not modify the link that theme dependent icons -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_hj8rtnfg7um.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_lbnruvf0jn.css">


<link  rel="stylesheet" href="/css/main.css" />


  <link id="highlight-css" rel="stylesheet" href="/css/highlight.css" />
  
    <link id="highlight-css-dark" rel="stylesheet" href="/css/highlight-dark.css" />
  




  <script id="fluid-configs">
    var Fluid = window.Fluid || {};
    Fluid.ctx = Object.assign({}, Fluid.ctx)
    var CONFIG = {"hostname":"sweetshance.github.io","root":"/","version":"1.9.4","typing":{"enable":true,"typeSpeed":70,"cursorChar":"_","loop":false,"scope":[]},"anchorjs":{"enable":true,"element":"h1,h2,h3,h4,h5,h6","placement":"left","visible":"hover","icon":""},"progressbar":{"enable":true,"height_px":3,"color":"#29d","options":{"showSpinner":false,"trickleSpeed":100}},"code_language":{"enable":true,"default":"TEXT"},"copy_btn":true,"image_caption":{"enable":true},"image_zoom":{"enable":true,"img_url_replace":["",""]},"toc":{"enable":true,"placement":"right","headingSelector":"h1,h2,h3,h4,h5,h6","collapseDepth":0},"lazyload":{"enable":true,"loading_img":"/img/loading.gif","onlypost":false,"offset_factor":2},"web_analytics":{"enable":false,"follow_dnt":true,"baidu":null,"google":null,"gtag":null,"tencent":{"sid":null,"cid":null},"woyaola":null,"cnzz":null,"leancloud":{"app_id":null,"app_key":null,"server_url":null,"path":"window.location.pathname","ignore_local":false}},"search_path":"/local-search.xml"};

    if (CONFIG.web_analytics.follow_dnt) {
      var dntVal = navigator.doNotTrack || window.doNotTrack || navigator.msDoNotTrack;
      Fluid.ctx.dnt = dntVal && (dntVal.startsWith('1') || dntVal.startsWith('yes') || dntVal.startsWith('on'));
    }
  </script>
  <script  src="/js/utils.js" ></script>
  <script  src="/js/color-schema.js" ></script>
  


  
<meta name="generator" content="Hexo 5.4.2"></head>


<body>
  

  <header>
    

<div class="header-inner" style="height: 70vh;">
  <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand" href="/">
      <strong>ShanCe</strong>
    </a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                <span>首页</span>
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                <span>归档</span>
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                <i class="iconfont icon-category-fill"></i>
                <span>分类</span>
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/tags/">
                <i class="iconfont icon-tags-fill"></i>
                <span>标签</span>
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                <span>关于</span>
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" target="_self" href="javascript:;" data-toggle="modal" data-target="#modalSearch" aria-label="Search">
              <i class="iconfont icon-search"></i>
            </a>
          </li>
          
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" target="_self" href="javascript:;" aria-label="Color Toggle">
              <i class="iconfont icon-dark" id="color-toggle-icon"></i>
            </a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

  

<div id="banner" class="banner" parallax=true
     style="background: url('/img/default.png') no-repeat center center; background-size: cover;">
  <div class="full-bg-img">
    <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
      <div class="banner-text text-center fade-in-up">
        <div class="h2">
          
            <span id="subtitle" data-typed-text="二叉树概念"></span>
          
        </div>

        
          
  <div class="mt-3">
    
      <span class="post-meta mr-2">
        <i class="iconfont icon-author" aria-hidden="true"></i>
        ShanCe
      </span>
    
    
      <span class="post-meta">
        <i class="iconfont icon-date-fill" aria-hidden="true"></i>
        <time datetime="2023-12-19 16:23" pubdate>
          2023年12月19日 下午
        </time>
      </span>
    
  </div>

  <div class="mt-1">
    
      <span class="post-meta mr-2">
        <i class="iconfont icon-chart"></i>
        
          3.1k 字
        
      </span>
    

    
      <span class="post-meta mr-2">
        <i class="iconfont icon-clock-fill"></i>
        
        
        
          27 分钟
        
      </span>
    

    
    
      
        <span id="busuanzi_container_page_pv" style="display: none">
          <i class="iconfont icon-eye" aria-hidden="true"></i>
          <span id="busuanzi_value_page_pv"></span> 次
        </span>
        
      
    
  </div>


        
      </div>

      
    </div>
  </div>
</div>

</div>

  </header>

  <main>
    
      

<div class="container-fluid nopadding-x">
  <div class="row nomargin-x">
    <div class="side-col d-none d-lg-block col-lg-2">
      

    </div>

    <div class="col-lg-8 nopadding-x-md">
      <div class="container nopadding-x-md" id="board-ctn">
        <div id="board">
          <article class="post-content mx-auto">
            <!-- SEO header -->
            <h1 style="display: none">二叉树概念</h1>
            
            
              <div class="markdown-body">
                
                <p><img src="/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-1.png" srcset="/img/loading.gif" lazyload alt="二叉树"></p>
<p>是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。<br>注意：</p>
<ol>
<li>每个节点最多有两颗子树，也就是度不大于2</li>
<li>左子树和右子树是有定义的，不能颠倒，即使某个节点只有一颗子树，也有左右之分</li>
</ol>
<h3 id="1-概念"><a href="#1-概念" class="headerlink" title="1. 概念"></a>1. 概念</h3><ol>
<li><strong>根节点</strong>：一个树只有一个树根，例如上图 A 就是整个树的根节点</li>
<li><strong>节点</strong>: 一个树包含多个元素和指向元素的分支，其中元素就是节点，例如：B C D E 等都是树的节点</li>
<li><strong>度</strong>: 一个节点拥有的子节点数，比如A节点的度为2，在 二叉树中度可能是 0 1 2</li>
<li><strong>叶子节点</strong>: 度为0的节点称为叶子节点，例如上图的：G E H I</li>
<li><strong>层次</strong>: 从根节点算，根为第一层，根的孩子为第二层，依次往下。比如 G 在 第4 层</li>
<li><strong>深度</strong>: 指数的最大层次。</li>
<li><strong>兄弟节点</strong>： 同一个根节点的结节点， 例如： B C 节点</li>
<li><strong>堂兄弟节点</strong>：双亲在同一层的节点互为堂兄弟节点；如上图：D E F 互为堂兄弟节点</li>
<li><strong>子孙节点</strong>：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙</li>
<li><strong>有序树</strong>：树中任意节点的子节点之间有顺序关系，这种树称为有序树</li>
<li><strong>无序树</strong>：树中任意节点的子节点之间没有顺序关系，这种树称为无序树,也称为自由树 </li>
</ol>
<h3 id="2-二叉树性质"><a href="#2-二叉树性质" class="headerlink" title="2.二叉树性质"></a>2.二叉树性质</h3><ol>
<li>二叉树中，第i层最多有 2<sup>(i-1)</sup> 个节点</li>
<li>如果二叉树的深度为 K, 那么此二叉树最多有 2<sup>k</sup> - 1 个节点</li>
<li>如果叶子节点个数为 n<sub>0</sub>, 度为2的节点个数为 n<sub>1</sub> 那么有：n<sub>0</sub> =  n<sub>1</sub>  + 1</li>
<li>具有n 个节点的满二叉树深为 log<sub>2</sub>(n+1)</li>
</ol>
<h3 id="3-根节点的五种形态"><a href="#3-根节点的五种形态" class="headerlink" title="3.根节点的五种形态"></a>3.根节点的五种形态</h3><ol>
<li>空二叉树</li>
<li>只有一个根节点</li>
<li>根节点只有左子树</li>
<li>根节点只有右子树</li>
<li>根节点既有左子树又有右子树</li>
</ol>
<h3 id="4-特殊二叉树"><a href="#4-特殊二叉树" class="headerlink" title="4.特殊二叉树"></a>4.特殊二叉树</h3><h4 id="4-1-满二叉树"><a href="#4-1-满二叉树" class="headerlink" title="4.1 满二叉树"></a>4.1 满二叉树</h4><p>如果一棵树只有度为0的节点和度为2的节点，并且度为0的节点在同一层，这棵树就是满二叉树<br><img src="/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-2.webp" srcset="/img/loading.gif" lazyload alt="二叉树"><br>满二叉树除了满足普通的二叉树性质，还具有一下性质</p>
<ol>
<li>满二叉树的第i层节点树为2<sup>(i-1)</sup></li>
<li>深度为k的满二叉树必有 2<sup>K</sup> - 1 个节点，叶子节点数为 2<sup> k - 1</sup></li>
<li>满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。</li>
<li>具有n个节点的满二叉树的深度为 log<sub>2</sub>(n+1)层</li>
</ol>
<h4 id="4-2-完全二叉树"><a href="#4-2-完全二叉树" class="headerlink" title="4.2 完全二叉树"></a>4.2 完全二叉树</h4><p>如果二叉树中除去最后一层节点为满二叉树，且最后一层的节点依次从左到右分布，则此二叉树被称为完全二叉树<br><img src="/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-3.jpg" srcset="/img/loading.gif" lazyload alt="二叉树"><br>完全二叉树除了满足普通二叉树的性质外，还满足：</p>
<ol>
<li>n个节点的完全二叉树的深度 ⌊log2n⌋ + 1 （注：⌊ ⌋表示向下取整）</li>
<li>对于任意一个完全二叉树来说，如果将含有的节点按照层次从左到右依次标号，对于任意一个节点 i ，完全二叉树还有以下几个结论成立：</li>
<li>1 当i &gt; 1 时，父节点为⌊ i/2 ⌋ (如上图)</li>
<li>2 如果 2*i &gt; n(总节点的个数), 则节点 i 肯定没有左孩子(左叶子节点)，否则其左孩子是节点 2*i</li>
<li>3 如果 2*i+1 &gt; n(总节点的个数), 则节点i 肯定没有右孩子(右子节点), 否则其右孩子是节点 2*i+1</li>
</ol>
<h4 id="4-3-二叉搜索树-又称：二叉排序树、二叉查找树"><a href="#4-3-二叉搜索树-又称：二叉排序树、二叉查找树" class="headerlink" title="4.3 二叉搜索树(又称：二叉排序树、二叉查找树)"></a>4.3 二叉搜索树(又称：二叉排序树、二叉查找树)</h4><p>二叉搜索树：可以是空树，或者是具备如下性质<br><img src="/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-4.webp" srcset="/img/loading.gif" lazyload alt="二叉树"></p>
<h5 id="二叉搜索树特点"><a href="#二叉搜索树特点" class="headerlink" title="二叉搜索树特点"></a>二叉搜索树特点</h5><ol>
<li>若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值</li>
<li>若任意节点的右子树不空，则右子树上所有节点的值均大于他的根节点的值</li>
<li>任意节点的左、右子树也分别为二叉搜索树;<br>特殊情况<br><img src="/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-5.webp" srcset="/img/loading.gif" lazyload alt="二叉树"><br>这种情况下，二叉搜索树已经变更为链表，搜索一个元素的时间复杂度从O(log<sub>2</sub>n )退化为O(n), 出现这种情况的原因是二叉搜索树没有自平衡的机制，所以就有了平衡二叉树。</li>
</ol>
<h4 id="4-4-平衡二叉树"><a href="#4-4-平衡二叉树" class="headerlink" title="4.4 平衡二叉树"></a>4.4 平衡二叉树</h4><p>平衡二叉树是一种二叉排序树，其中每个节点的左子树和右子树的高度差之多等于1，它是二叉排序树的一个进化体，实现方式有：红黑树、AVL树</p>
<p><img src="/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-6.webp" srcset="/img/loading.gif" lazyload alt="二叉树"></p>
<p><strong>平衡因子</strong>: 平衡二叉树是在二叉查找树的基础上进行构建，为了维持平衡二叉树的平衡，那么就需要一种机制来判断平衡二叉树是否是平衡的。这种机制就叫做平衡因子。平衡二叉树上某个节点的<strong>左子树深度</strong>减去<strong>右子树深度</strong>的值，就称为<strong>此节点的平衡因子</strong>。</p>
<p><strong>最小不平衡树</strong>: 距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树，就称为最小不平衡树。</p>
<h5 id="平衡二叉树特点"><a href="#平衡二叉树特点" class="headerlink" title="平衡二叉树特点"></a>平衡二叉树特点</h5><ol>
<li>平衡二叉树是一种二叉查找树</li>
<li>每个节点的左子树的高度减去右子树的高度的绝对值不超过1</li>
<li>空树和左右子树都是平衡二叉树</li>
<li>相比红黑树，平衡二叉树比较适用于没有删除的情况</li>
</ol>
<h5 id="左旋"><a href="#左旋" class="headerlink" title="左旋"></a>左旋</h5><p>是指将根节点的右侧往左拉，原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点。<br><img src="/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-7.webp" srcset="/img/loading.gif" lazyload alt="二叉树"></p>
<h5 id="右旋"><a href="#右旋" class="headerlink" title="右旋"></a>右旋</h5><p>将根节点的左节点往右拉，原先的左子节点变成新的父节点，并把多余的右节点出让，给已经降级的根节点充当左子节点。<br><img src="/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-8.webp" srcset="/img/loading.gif" lazyload alt="二叉树"></p>
<h5 id="失衡"><a href="#失衡" class="headerlink" title="失衡"></a>失衡</h5><p>当我们在一个平衡二叉树上插入一个节点时，有可能会导致失衡，即出现平衡因子绝对值大于1的节点，如下图，当插入节点后，其中key 为53的节点失去平衡，我们称该节点为<strong>失衡节点</strong>，必须重新调整树的结构使之恢复平衡。</p>
<p><img src="/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-9.webp" srcset="/img/loading.gif" lazyload alt="二叉树"><br>不一定只有一个节点失去平衡，有可能插入一个节点会让多个节点失衡。这时候找<strong>最小的平衡子树的根节点作为失衡节点</strong>。</p>
<h5 id="恢复平衡"><a href="#恢复平衡" class="headerlink" title="恢复平衡"></a>恢复平衡</h5><p>失衡的四种类型<br><img src="/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-10.jpg" srcset="/img/loading.gif" lazyload alt="二叉树"><br>如第一个，当平衡二叉树为AB时，插入一个C节点，使得失衡了，失衡节点为A，此时因为C节点插入的位置为失衡节点的左孩子的左孩子，所以是LL型，以此类推。</p>
<p>恢复平衡要保持二叉搜索树的原则，<strong>把key的值中等的作为根节点，最小的放在左孩子，最大的放到右孩子</strong>。通过这一目的实现降低树的深度。<br><img src="/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-11.jpg" srcset="/img/loading.gif" lazyload alt="二叉树"></p>
<h4 id="4-5-AVL树"><a href="#4-5-AVL树" class="headerlink" title="4.5 AVL树"></a>4.5 AVL树</h4><p>AVL树本质还是一棵二叉搜索树</p>
<ol>
<li>本身是一棵二叉搜索树</li>
<li>带有平衡条件：每个节点的左右子树的深度之差的绝对值（平衡因子）最多为1，也就是说AVL树，本质是呆了平衡功能的二叉查找树</li>
</ol>
<p>如果在AVL树中插入或删除节点后，使得高度之差大于1。此时，AVL树的平衡状态就被破坏，它就不再是一棵二叉树；为了让它重新维持在一个平衡状态，就需要对其进行旋转处理。AVL实现平衡的关键在于旋转操作。</p>
<p><strong>注意</strong>： 平衡二叉树和VAL树都是高效的二叉查找树，它们的区别在于<strong>平衡条件</strong>和<strong>查找效率</strong>上。平衡二叉树的<strong>平衡条件更为严格</strong>，而VAL树的自平衡特性使得它在<strong>插入和删除操作时能够更快地调整树的形状</strong>。</p>
<h4 id="4-6-红黑树"><a href="#4-6-红黑树" class="headerlink" title="4.6 红黑树"></a>4.6 红黑树</h4><p>是一种<strong>二叉搜索树</strong>，但在<strong>每个节点上增加一个存储位表示节点的颜色</strong>，可以是Red或Black。 通过任何一条从根到叶子的路径上各个节点着色方式的限制，<strong>红黑树确保没有一条路径会比其他路径长出俩倍</strong>，因而是接近平衡的。因而，红黑树是<strong>相对接近平衡的二叉树</strong>，并不是一个完美平衡二叉查找树<br><img src="/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-12.webp" srcset="/img/loading.gif" lazyload alt="二叉树"><br>规则：</p>
<ol>
<li>节点不是黑色，就是红色(非黑即红)</li>
<li>根节点为黑色</li>
<li>叶子节点为黑色(叶子节点是指末梢的空节点 nil 或者 null)</li>
<li>一个节点为红色，则其两个子节点必须是黑色(根到叶子节点的所有路径，不可能存在两个连续的红色节点)</li>
<li>每个节点到叶子节点的所有路径，都包含相同数目的黑色节点（相同的黑色高度）</li>
</ol>
<h5 id="红黑树的应用"><a href="#红黑树的应用" class="headerlink" title="红黑树的应用"></a>红黑树的应用</h5><ol>
<li>java中，TreeMap、TreeSet都使用红黑树作为底层数据结构</li>
<li>JDK 1.8开始，HashMap也引入了红黑树：当冲突的链表长度超过8时，自动转为红黑树</li>
<li>Linux底层的CFS进程调度算法中，vruntime使用红黑树进行存储。</li>
<li>多路复用技术的Epoll，其核心结构是红黑树 + 双向链表</li>
</ol>
<h3 id="5-二叉树的存储结构"><a href="#5-二叉树的存储结构" class="headerlink" title="5. 二叉树的存储结构"></a>5. 二叉树的存储结构</h3><p>二叉树一般可以使用两种结构存储，一种<strong>顺序结构</strong>，一种<strong>链式结构</strong></p>
<h4 id="5-1-顺序存储"><a href="#5-1-顺序存储" class="headerlink" title="5.1 顺序存储"></a>5.1 顺序存储</h4><p>顺序存储就是使用<strong>数组来存储</strong>，一般使用数组只适合表示完全二叉树，因为<strong>不完全二叉树会有空间的浪费</strong>。现实使用中<strong>只有堆才会使用数组来存储</strong></p>
<p>对于完全二叉树的存储，仅需对其从根节点开始仅需编号，使用数组存储编号即可。取出式依据完全二叉树由左到右分布的性质恢复即可。<br><img src="/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-14.webp" srcset="/img/loading.gif" lazyload alt="二叉树"></p>
<h4 id="5-2-链式存储"><a href="#5-2-链式存储" class="headerlink" title="5.2 链式存储"></a>5.2 链式存储</h4><p>二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个节点由三个域组成，数据域和左右指针域，左右指针分别用来给出该节点左孩子和右孩子所在的链节点的存储地址 。<br><img src="/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-15.1.webp" srcset="/img/loading.gif" lazyload alt="二叉树"><br><img src="/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-15.2.png" srcset="/img/loading.gif" lazyload alt="二叉树"><br><img src="/images/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%911-15.3.webp" srcset="/img/loading.gif" lazyload alt="二叉树"></p>

                
              </div>
            
            <hr/>
            <div>
              <div class="post-metas my-3">
  
    <div class="post-meta mr-3 d-flex align-items-center">
      <i class="iconfont icon-category"></i>
      

<span class="category-chains">
  
  
    
      <span class="category-chain">
        
  <a href="/categories/%E7%AE%97%E6%B3%95%E5%AD%A6%E4%B9%A0/" class="category-chain-item">算法学习</a>
  
  

      </span>
    
  
</span>

    </div>
  
  
    <div class="post-meta">
      <i class="iconfont icon-tags"></i>
      
        <a href="/tags/%E4%BA%8C%E5%8F%89%E6%A0%91/">#二叉树</a>
      
    </div>
  
</div>


              
  

  <div class="license-box my-3">
    <div class="license-title">
      <div>二叉树概念</div>
      <div>https://sweetshance.github.io/2023/12/19/算法/二叉树/1.二叉树概念/</div>
    </div>
    <div class="license-meta">
      
        <div class="license-meta-item">
          <div>作者</div>
          <div>ShanCe</div>
        </div>
      
      
        <div class="license-meta-item license-meta-date">
          <div>发布于</div>
          <div>2023年12月19日</div>
        </div>
      
      
      
    </div>
    <div class="license-icon iconfont"></div>
  </div>



              
                <div class="post-prevnext my-3">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/2023/12/21/%E7%AE%97%E6%B3%95/%E4%BA%8C%E5%8F%89%E6%A0%91/2-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86/" title="2.二叉树的遍历">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">2.二叉树的遍历</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/2023/12/12/mysql/%E5%88%9B%E5%BB%BA%E7%94%A8%E6%88%B7%E5%88%86%E9%85%8D%E6%9D%83%E9%99%90/" title="mysql 创建用户分配权限">
                        <span class="hidden-mobile">mysql 创建用户分配权限</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
          </article>
        </div>
      </div>
    </div>

    <div class="side-col d-none d-lg-block col-lg-2">
      
  <aside class="sidebar" style="margin-left: -1rem">
    <div id="toc">
  <p class="toc-header">
    <i class="iconfont icon-list"></i>
    <span>目录</span>
  </p>
  <div class="toc-body" id="toc-body"></div>
</div>



  </aside>


    </div>
  </div>
</div>





  



  



  



  



  







    

    
      <a id="scroll-top-button" aria-label="TOP" href="#" role="button">
        <i class="iconfont icon-arrowup" aria-hidden="true"></i>
      </a>
    

    
      <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v" for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>

    

    
  </main>

  <footer>
    <div class="footer-inner">
  
    <div class="footer-content">
       <a href="http://82.157.172.231/" target="_blank" rel="nofollow noopener"><span>无聊</span></a> <i class="iconfont icon-love"></i> <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener"><span>ShanCe</span></a> 
    </div>
  
  
    <div class="statistics">
  
  

  
    
      <span id="busuanzi_container_site_pv" style="display: none">
        总访问量 
        <span id="busuanzi_value_site_pv"></span>
         次
      </span>
    
    
      <span id="busuanzi_container_site_uv" style="display: none">
        总访客数 
        <span id="busuanzi_value_site_uv"></span>
         人
      </span>
    
    
  
</div>

  
  
  
</div>

  </footer>

  <!-- Scripts -->
  
  <script  src="https://lib.baomitu.com/nprogress/0.2.0/nprogress.min.js" ></script>
  <link  rel="stylesheet" href="https://lib.baomitu.com/nprogress/0.2.0/nprogress.min.css" />

  <script>
    NProgress.configure({"showSpinner":false,"trickleSpeed":100})
    NProgress.start()
    window.addEventListener('load', function() {
      NProgress.done();
    })
  </script>


<script  src="https://lib.baomitu.com/jquery/3.6.0/jquery.min.js" ></script>
<script  src="https://lib.baomitu.com/twitter-bootstrap/4.6.1/js/bootstrap.min.js" ></script>
<script  src="/js/events.js" ></script>
<script  src="/js/plugins.js" ></script>


  <script  src="https://lib.baomitu.com/typed.js/2.0.12/typed.min.js" ></script>
  <script>
    (function (window, document) {
      var typing = Fluid.plugins.typing;
      var subtitle = document.getElementById('subtitle');
      if (!subtitle || !typing) {
        return;
      }
      var text = subtitle.getAttribute('data-typed-text');
      
        typing(text);
      
    })(window, document);
  </script>




  
    <script  src="/js/img-lazyload.js" ></script>
  




  
<script>
  Fluid.utils.createScript('https://lib.baomitu.com/tocbot/4.18.2/tocbot.min.js', function() {
    var toc = jQuery('#toc');
    if (toc.length === 0 || !window.tocbot) { return; }
    var boardCtn = jQuery('#board-ctn');
    var boardTop = boardCtn.offset().top;

    window.tocbot.init(Object.assign({
      tocSelector     : '#toc-body',
      contentSelector : '.markdown-body',
      linkClass       : 'tocbot-link',
      activeLinkClass : 'tocbot-active-link',
      listClass       : 'tocbot-list',
      isCollapsedClass: 'tocbot-is-collapsed',
      collapsibleClass: 'tocbot-is-collapsible',
      scrollSmooth    : true,
      includeTitleTags: true,
      headingsOffset  : -boardTop,
    }, CONFIG.toc));
    if (toc.find('.toc-list-item').length > 0) {
      toc.css('visibility', 'visible');
    }

    Fluid.events.registerRefreshCallback(function() {
      if ('tocbot' in window) {
        tocbot.refresh();
        var toc = jQuery('#toc');
        if (toc.length === 0 || !tocbot) {
          return;
        }
        if (toc.find('.toc-list-item').length > 0) {
          toc.css('visibility', 'visible');
        }
      }
    });
  });
</script>


  <script src=https://lib.baomitu.com/clipboard.js/2.0.11/clipboard.min.js></script>

  <script>Fluid.plugins.codeWidget();</script>


  
<script>
  Fluid.utils.createScript('https://lib.baomitu.com/anchor-js/4.3.1/anchor.min.js', function() {
    window.anchors.options = {
      placement: CONFIG.anchorjs.placement,
      visible  : CONFIG.anchorjs.visible
    };
    if (CONFIG.anchorjs.icon) {
      window.anchors.options.icon = CONFIG.anchorjs.icon;
    }
    var el = (CONFIG.anchorjs.element || 'h1,h2,h3,h4,h5,h6').split(',');
    var res = [];
    for (var item of el) {
      res.push('.markdown-body > ' + item.trim());
    }
    if (CONFIG.anchorjs.placement === 'left') {
      window.anchors.options.class = 'anchorjs-link-left';
    }
    window.anchors.add(res.join(', '));

    Fluid.events.registerRefreshCallback(function() {
      if ('anchors' in window) {
        anchors.removeAll();
        var el = (CONFIG.anchorjs.element || 'h1,h2,h3,h4,h5,h6').split(',');
        var res = [];
        for (var item of el) {
          res.push('.markdown-body > ' + item.trim());
        }
        if (CONFIG.anchorjs.placement === 'left') {
          anchors.options.class = 'anchorjs-link-left';
        }
        anchors.add(res.join(', '));
      }
    });
  });
</script>


  
<script>
  Fluid.utils.createScript('https://lib.baomitu.com/fancybox/3.5.7/jquery.fancybox.min.js', function() {
    Fluid.plugins.fancyBox();
  });
</script>


  <script>Fluid.plugins.imageCaption();</script>

  <script  src="/js/local-search.js" ></script>

  <script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>





<!-- 主题的启动项，将它保持在最底部 -->
<!-- the boot of the theme, keep it at the bottom -->
<script  src="/js/boot.js" ></script>


  

  <noscript>
    <div class="noscript-warning">博客在允许 JavaScript 运行的环境下浏览效果更佳</div>
  </noscript>
</body>
</html>
